#include <func.h>

#define CHECK_INSERT 1

#define rb_parent(r)   ((r)->parent)
#define rb_color(r) ((r)->color)
#define rb_is_red(r)   ((r)->color==RED)
#define rb_is_black(r)  ((r)->color==BLACK)
#define rb_set_black(r)  do { (r)->color = BLACK; } while (0)
#define rb_set_red(r)  do { (r)->color = RED; } while (0)
#define rb_set_parent(r,p)  do { (r)->parent = (p); } while (0)
#define rb_set_color(r,c)  do { (r)->color = (c); } while (0)

#define RED        0    // 红色节点
#define BLACK    1    // 黑色节点

typedef int Type;

//红黑树节点
typedef struct RBTreeNode{
    unsigned char color;
    Type key;
    struct RBTreeNode* left;
    struct RBTreeNode* right;
    struct RBTreeNode* parent;
}Node,*RBTree;

//红黑树的树根
typedef struct {
    Node* node;
}RBRoot;

// 打印红黑树
void print_rbtree(RBRoot* root);

//插入函数--只是申请新节点
void insert_rbtree(RBRoot *root,Type element);

//调整函数
void rbtree_insert_fixup(RBRoot* root, Node* node);

//左旋
void rbtree_left_rotate(RBRoot* root,Node* x);
//右旋
void rbtree_right_rotate(RBRoot* root, Node* y);